package tasks.zhuanyeji.微服务管理;

import java.util.*;

public class Solution {

    /**
     * 计算部署所有微服务所需的最少服务器数量
     *
     * @param memory      每个微服务所需的内存（数组）
     * @param maxCapacity 每台服务器最大容量
     * @return 最少需要的服务器数量；若无法部署（某个服务 > 容量），返回 -1
     */
    public static int minServersNeeded(int[] memory, int maxCapacity) {
        // 边界情况处理
        if (memory == null || memory.length == 0) {
            return 0;
        }

        // 检查是否有单个微服务超过服务器容量
        for (int mem : memory) {
            if (mem > maxCapacity) {
                return -1; // 无法部署
            }
        }

        // 1. 将微服务按内存需求降序排列（关键步骤）
        Arrays.sort(memory);
        // reverse 数组，因为 Arrays.sort 是升序
        reverseArray(memory);

        // 2. 存储每台服务器当前已使用的内存
        List<Integer> servers = new ArrayList<>();

        // 3. 遍历每个微服务
        for (int need : memory) {
            boolean placed = false;

            // 尝试放入现有的服务器（首次适应：找到第一个能放下的）
            for (int i = 0; i < servers.size(); i++) {
                int used = servers.get(i);
                if (used + need <= maxCapacity) {
                    servers.set(i, used + need); // 更新该服务器的使用量
                    placed = true;
                    break; // 放入后跳出循环
                }
            }

            // 如果没找到合适服务器，新建一台
            if (!placed) {
                servers.add(need);
            }
        }

        return servers.size();
    }

    /**
     * 手动反转数组（Java 的 Arrays.sort 无法直接降序基本类型）
     */
    private static void reverseArray(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }

    // ========== 测试主函数 ==========
    public static void main(String[] args) {
        int[] memory = {4, 8, 1, 4, 2, 1};
        int maxCapacity = 8;

        int result = minServersNeeded(memory, maxCapacity);
        System.out.println("最少需要 " + result + " 台服务器"); // 输出：3
    }
}
